//排序数组 （分治-归并实现）
//测试链接 https://leetcode.cn/problems/sort-an-array/
public class SortArray {
    int[] help; //创建辅助数组
    public int[] sortArray(int[] nums) {
        int n = nums.length;
        help = new int[n]; //申请空间
        mergeSort(nums, 0 ,n-1);
        return nums;
    }

    public void mergeSort(int[] nums, int left, int right){
        if(left >= right) return; //递归结束条件

        int mid = left + (right - left)/2;
        //此时区间被划分为： [left,mid],  [mid+1, right]

        mergeSort(nums,left,mid);    //排序左部分
        mergeSort(nums,mid+1,right); //排序右部分

        //排序结束，合并left 到 right的区间
        int cur1 = left, cur2 = mid+1, i = left;
        while(cur1 <= mid && cur2 <= right){
            help[i++] = nums[cur1] <= nums[cur2] ? nums[cur1++] : nums[cur2++];
        }
        //处理剩余情况
        while(cur1 <= mid)  help[i++] = nums[cur1++];
        while(cur2 <= right)  help[i++] = nums[cur2++];

        //将排好序的数组重新刷回原数组
        for(int j = left; j <= right; j++){
            nums[j] = help[j];
        }
    }
}
